﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace CPF_experement
{
    class GDD
    {
        public LinkedList<MDDNode>[] levels;
        int agentNum;
        int mddNum;

        public GDD(int mddNum, int agentNum, int start_Pos_X, int start_pos_y, int cost,int maxCostOnLevel, int numOfAgents)
        {
            this.mddNum = mddNum;
            this.agentNum=agentNum;
            levels = new LinkedList<MDDNode>[maxCostOnLevel + 1];
            Hashtable closedList = new Hashtable();
            LinkedList<MDDNode> children;
            for (int i = 0; i <= maxCostOnLevel; i++)
            {
                levels[i] = new LinkedList<MDDNode>();
            }
            MDDNode toAdd = new MDDNode(start_Pos_X, start_pos_y,0 , numOfAgents, this);
            LinkedListNode<MDDNode> llNode = new LinkedListNode<MDDNode>(toAdd);
            toAdd.setMyNode(llNode);
            levels[0].AddFirst(llNode);
            for (int i = 0; i < maxCostOnLevel ; i++)
            {
                int hur = cost - i - 1;
                if (hur < 0)
                {
                    hur = 0;
                }
                LinkedListNode<MDDNode> temp = levels[i].First;
                while (temp!=null)
                {
                    LinkedListNode<MDDNode> child;
                    children = True_Path_Huristic.getNextLevelForTile(temp.Value.getX(), temp.Value.getY(), agentNum, hur);
                    child = children.First;
                    while (child != null)
                    {
                        toAdd = child.Value;
                        if (closedList.Contains(toAdd))
                        {
                            toAdd = (MDDNode)closedList[toAdd];
                        }
                        else
                        {
                            toAdd = new MDDNode(toAdd,i+1 , numOfAgents,this);
                            closedList.Add(toAdd,toAdd);
                            llNode = new LinkedListNode<MDDNode>(toAdd);
                            toAdd.setMyNode(llNode);
                            levels[i + 1].AddLast(llNode);
                        }
                        temp.Value.addChild(toAdd);
                        toAdd.addParent(temp.Value);

                        child = child.Next;
                    }


                    temp=temp.Next;
                }
                closedList.Clear();
            }
            levels[0].First.Value.startOrGoal = true;
            levels[maxCostOnLevel].First.Value.startOrGoal = true;
        }
        //public GDD(GDD cpy)
        //{

        //}
        public bool syncGDDs(GDD other, int setUntil)
        {
            bool validParent;
            LinkedListNode<MDDNode> parent;
            MDDNode parentToDelete;
            LinkedListNode<MDDNode> toSetCoexisting;
            LinkedListNode<MDDNode> tempToSetCoexisting;
            LinkedList<MDDNode> coexitingForNodeLL = new LinkedList<MDDNode>();
            HashSet<MDDNode> coexitingForNodeHS = new HashSet<MDDNode>();

            coexitingForNodeLL.AddFirst(other.levels[0].First.Value);
            levels[0].First.Value.setCoexist(coexitingForNodeLL, other.mddNum);

            for (int i = 1; i < levels.Length; i++)
            {
                toSetCoexisting = levels[i].First;
                while (toSetCoexisting != null)
                {
                    coexitingForNodeLL = new LinkedList<MDDNode>();
                    coexitingForNodeHS.Clear();
                    

                    parent=toSetCoexisting.Value.parents.First;
                    while (parent!=null)
                    {
                        validParent = false;
                        foreach (MDDNode coexist in parent.Value.coexistLinkedList[other.mddNum])
                        {
                            foreach (MDDNode chield in coexist.children)
                            {
                                if (!toSetCoexisting.Value.Equals(chield))
                                {
                                    if (!parent.Value.Equals(chield) || !toSetCoexisting.Value.Equals(coexist))
                                    {
                                        if (toSetCoexisting.Value.isCoexistingWithOtherMDDs(chield, other.mddNum))
                                        {
                                            validParent = true;

                                            if (!coexitingForNodeHS.Contains(chield))
                                            {
                                                coexitingForNodeHS.Add(chield);
                                                coexitingForNodeLL.AddFirst(chield);
                                                chield.addIsCoexisting(toSetCoexisting.Value, mddNum);
                                            }
                                        }
                                    }
                                }
                            }
                        }
                        parentToDelete = parent.Value;
                        parent = parent.Next;
                        if (!validParent)
                        {
                            toSetCoexisting.Value.removeParent(parentToDelete);
                        }
                    }
                    toSetCoexisting.Value.setCoexist(coexitingForNodeLL, other.mddNum);
                    toSetCoexisting.Value.setUntil = setUntil;
                    tempToSetCoexisting = toSetCoexisting;
                    toSetCoexisting = toSetCoexisting.Next;
                    if (tempToSetCoexisting.Value.getCoexistCount(other.mddNum) == 0)
                    {
                        tempToSetCoexisting.Value.delete();
                    }
                }
                if (levels[1].Count == 0)
                {
                    return false;
                }
            }
            //if (setUntil==agentNum-1)
            //{

            //}
            return true;
        }



        public int getMddNum()
        {
            return mddNum;
        }
        public int getAgentNum()
        {
            return mddNum;
        }

        public void printGDD()
        {
            Console.WriteLine();
            Console.WriteLine();
            for (int j = 0; j < levels.Count(); j++)
            {
                Console.WriteLine("\n\nlevel: " + j + " total- " + levels[j].Count+"  *****");
                Console.WriteLine("------------------");
                foreach (MDDNode node in levels[j])
                {
                    Console.Write("\n\n-node- (" + node.getX() + "," + node.getY() + ") children: ");
                    foreach (MDDNode chield in node.children)
                    {
                        Console.Write("(" + chield.getX() + "," + chield.getY() + ") ");
                    }
                    Console.Write(" parents: ");
                    foreach (MDDNode parent in node.parents)
                    {
                        Console.Write("(" + parent.getX() + "," + parent.getY() + ") ");
                    }
                    Console.Write(" coexist: ");
                    int i = 0;
                    foreach (LinkedList<MDDNode> coexistList in node.coexistLinkedList)
                    {
                        Console.Write(" for agent - " + i++);
                        foreach (MDDNode coexist in coexistList)
                        {
                            Console.Write("(" + coexist.getX() + "," + coexist.getY() + ") ");
                        }
                    }
                }
            }
        }
    }
    class MDDNode
    {
        int pos_X;
        int pos_Y;
        public int level;
        public int setUntil;
        public LinkedList<MDDNode> children;
        public LinkedList<MDDNode> parents;
        public LinkedList<MDDNode>[] coexistLinkedList;
        //Hashtable[] coexistHashTable;
        LinkedList<MDDNode>[] is_coexisting;
        GDD father;
        LinkedListNode<MDDNode> myNode;
        public bool startOrGoal;

        public MDDNode(int pos_X, int pos_Y,int level, int numOfAgents, GDD father)
        {
            this.pos_X = pos_X;
            this.pos_Y = pos_Y;
            this.level = level;
            this.father = father;
            setUntil = 0;
            children = new LinkedList<MDDNode>();
            parents = new LinkedList<MDDNode>();
            coexistLinkedList = new LinkedList<MDDNode>[numOfAgents];
            //coexistHashTable = new Hashtable[numOfAgents];
            is_coexisting = new LinkedList<MDDNode>[numOfAgents];
            for (int i = 0; i < numOfAgents; i++)
            {
                is_coexisting[i] = new LinkedList<MDDNode>();
                //coexistHashTable[i] = new Hashtable();
                coexistLinkedList[i] = new LinkedList<MDDNode>();
            }
        }
        public MDDNode(MDDNode cpy,int level, int numOfAgents, GDD father)
        {
            this.pos_X = cpy.pos_X;
            this.pos_Y = cpy.pos_Y;
            this.father = father;
            this.level = level;
            children = new LinkedList<MDDNode>();
            parents = new LinkedList<MDDNode>();
            coexistLinkedList = new LinkedList<MDDNode>[numOfAgents];
            //coexistHashTable = new Hashtable[numOfAgents];
            is_coexisting = new LinkedList<MDDNode>[numOfAgents];
            setUntil = 0;
            for (int i = 0; i < numOfAgents; i++)
            {
                is_coexisting[i] = new LinkedList<MDDNode>();
                //coexistHashTable[i] = new Hashtable();
                coexistLinkedList[i] = new LinkedList<MDDNode>();
            }
        }
        public MDDNode(int pos_X, int pos_Y)
        {
            this.pos_X = pos_X;
            this.pos_Y = pos_Y;
        }

        public void delete()
        {
            foreach (MDDNode parent in parents)
            {
                parent.children.Remove(this);
                parent.checkAndDelete();
            }
            foreach (MDDNode child in children)
            {
                child.parents.Remove(this);
                child.checkAndDelete();
            }
            //foreach (LinkedList<MDDNode> is_coexistList in is_coexisting)
            //{
            //    foreach (MDDNode coexistingForOther in is_coexistList)
            //    {
            //            coexistingForOther.coexistLinkedList[father.getAgentNum()].Remove(this);
            //            //coexisting.coexistHashTable[father.getAgentNum()].Remove(this);
            //            coexistingForOther.checkAndDelete();
            //    }
            //}
            //foreach (LinkedList<MDDNode> coexistList in coexistLinkedList)
            //{
            //    foreach (MDDNode coexisting in coexistList)
            //    {
            //        coexisting.is_coexisting[father.getAgentNum()].Remove(this);
            //    }
            //}
            myNode.List.Remove(myNode);
        }
        public void checkAndDelete()
        {
            if (!startOrGoal)
            {
                if (parents.Count == 0 || children.Count == 0)
                {
                    this.delete();
                    return;
                }
                    //for (int i = father.getAgentNum() + 1; i <= setUntil; i++)
                    //{
                    //    if (coexistLinkedList[i].Count == 0)
                    //    {
                    //        this.delete();
                    //        return;
                    //    }
                    //}
            }
        }

        public bool isCoexistingWithOtherMDDs(MDDNode toCheck, int otherAgent)
        {
            bool ans = false;
            for (int i = father.getMddNum() + 1 ; i < otherAgent; i++)
            {
                ans = false;
                foreach (MDDNode coexistingForOther in coexistLinkedList[i])
                {
                    if (coexistingForOther.coexistLinkedList[toCheck.father.getMddNum()].Contains(toCheck))
                    {
                        ans = true;
                        break;
                    }
                }
                if (!ans)
                    return false;
            }
            return true;
        }
        public bool OKwithOthers()
        {
            LinkedList<MDDNode>[] sortedCoexistLinkedList = new LinkedList<MDDNode>[coexistLinkedList.Length];
            for (int i = 0; i < coexistLinkedList.Length; i++)
            {
                sortedCoexistLinkedList[i] = coexistLinkedList[i];
            }
            Array.Sort(sortedCoexistLinkedList, delegate(LinkedList<MDDNode> list1, LinkedList<MDDNode> list2)
            {
                return list1.Count.CompareTo(list2.Count);
            });
            return !isConflicting(sortedCoexistLinkedList, sortedCoexistLinkedList.Length , 0, new Hashtable());
        }
        private bool isConflicting(LinkedList<MDDNode>[] sortedCoexistLinkedList, int index, int agentsSoFar, Hashtable possibleSteps)
        {
            int temp;
            if (agentsSoFar > possibleSteps.Count)
                return true;
            for (int i = index-1; i >= 0 ; i--)
            {
                if (sortedCoexistLinkedList[i].Count <= agentsSoFar+i)
                {
                    foreach (MDDNode Step in sortedCoexistLinkedList[i])
                    {
                        temp = Step.getX() * True_Path_Huristic.getGrisSize() + Step.getY();
                        if (possibleSteps.Contains(temp))
                        {
                            possibleSteps[temp] = (int)possibleSteps[temp] + 1;
                        }
                        else
                            possibleSteps.Add(temp, 1);
                    }

                    if (isConflicting(sortedCoexistLinkedList, i, agentsSoFar + 1, possibleSteps))
                        return true;

                    foreach (MDDNode Step in sortedCoexistLinkedList[i])
                    {
                        temp = Step.getX() * True_Path_Huristic.getGrisSize() + Step.getY();
                        if ((int)possibleSteps[temp] > 1)
                        {
                            possibleSteps[temp] = (int)possibleSteps[temp] - 1;
                        }
                        else
                            possibleSteps.Remove(temp);
                    }
                }
            }
            return false;
        }

        //public HashSet<MDDNode> getCoexistingForAllParents()
        //{
        //    HashSet<MDDNode> coexistingForParents = new HashSet<MDDNode>();
        //    foreach (MDDNode parent in parents)
        //    {
        //        foreach (MDDNode parentCoexist in parent.coexistLinkedList)
        //        {
        //            if (!coexistingForParents.Contains(parentCoexist))
        //            {
        //                coexistingForParents.Add(parentCoexist);
        //            }
        //        }
        //    }
        //    return coexistingForParents;
        //}

        //public bool isCoexisting( MDDNode original ,HashSet<MDDNode> coexistingForParents)
        //{
        //    if (this.Equals(original))
        //    {
        //        return false;
        //    }
        //        foreach (MDDNode parent in parents)
        //        {
        //            if (coexistingForParents.Contains(otherMDDParents))
        //            {
        //                if(!parent.Equals(original) || !
        //                return true;
        //            }
        //        }
        //        return false;
        //}
        public void removeParent(MDDNode parent)
        {
            parents.Remove(parent);
            parent.children.Remove(this);
            parent.checkAndDelete();
        }
        public void addParent(MDDNode parent)
        {
            parents.AddLast(parent);
        }
        public void addChild(MDDNode child)
        {
            children.AddLast(child);
        }
        public void setCoexist(LinkedList<MDDNode> coexists, int agentNum)
        {
            coexistLinkedList[agentNum] = coexists;
        }
        public void setMyNode(LinkedListNode<MDDNode> me)
        {
            myNode = me;
        }
        public void addIsCoexisting(MDDNode isCoexisting, int agentNum)
        {
            is_coexisting[agentNum].AddLast(isCoexisting);
        }
        public int getX()
        {
            return pos_X;
        }
        public int getY()
        {
            return pos_Y;
        }
        public override int GetHashCode()
        {
            return pos_X*pos_Y;
        }
        public override bool Equals(object obj)
        {
            MDDNode comp = (MDDNode)obj;
            return this.pos_X==comp.pos_X && this.pos_Y==comp.pos_Y;
        }
        public int getCoexistCount(int otherAgent)
        {
            return coexistLinkedList[otherAgent].Count;
        }
    }
}
